#pragma once

#include <vector>
#include <map>
#include <tuple>
#include <iostream>

using namespace std;

// Grafo implementado utilizando matriz de adjacência
template<typename V = char, typename E = char>
class AdjacenceMatrixGraph
{
  struct Element {
    bool active;
    E value;

    Element():
    active(false)
    {
    }
    
    Element(bool active, const E value):
    active(active),
    value(value)
    {
    }
  };

  vector<vector<Element>> _matrix;

  vector<V> _nodeValues;

  int _index;

  struct Pair
  {
    Pair(int max, int min): max(max), min(min) 
    {
    }
    int max;
    int min;
  };

  Pair makePair(int node1, int node2) const
  {
    return node1 > node2 ? Pair(node1, node2) : Pair(node2, node1);
  }
  
public:

  AdjacenceMatrixGraph(int n):
  _index(0),
  _matrix(n)
  {
    for (int i = 0; i<_matrix.size(); i++) {
      _matrix[i].reserve(n);
      _matrix[i].resize(n);
    }

    _nodeValues.reserve(n);
  }
  
  int addNode(const V &value = V())
  {
    _nodeValues.push_back(value);
    return _index++;
  }

  const V &getNodeValue(int n) const
  {
    return _nodeValues[n];
  }

  int countNodes() const
  {
    return _index;
  }

  int getNodeDegree(int node) const
  {
    int d = 0;
    for (int i = 0; i< _matrix.size(); i++) {
      Pair pair = makePair(node,i);
      if (_matrix[pair.max][pair.min].active) {
        d++;
      }
    }
    return d;
  }

  int countEdges() const
  {
    int c = 0;
    // começo da direita para esquerda
    for (int i = _index - 1; i > 0; i--) {
      // e de baixo para cima
      for (int j = i - 1; j >= 0; j--) {
        if (_matrix[i][j].active) {
          c++;
        }
      }
    }
    return c;
  }

  bool addEdge(int node1, int node2, const E &value = E())
  {
    if (node1 >= _index || node2 >= _index || node1 == node2) {
      return false;
    }

    Pair pair = makePair(node1, node2);

    // Adiciono só acima da diagonal principal 
    _matrix[pair.max][pair.min] = Element(true,value);
  
    return true;
  }
  
  bool areNodesAdjacents(int node1, int node2)
  {
    // FIXME: cópia de addEdge
    if (node1 >= _index || node2 >= _index || node1 == node2) {
      return false;
    }

    Pair pair = makePair(node1, node2);

    return _matrix[pair.max][pair.min].active;
  }
  
  const E &getEdgeValue(int node1, int node2) const
  {
    Pair pair = makePair(node1, node2);
    return _matrix[pair.max][pair.min].value;
  }

  vector<int> getAdjacentNodes(int node) const
  {
    vector<int> a;
    for (int i = 0; i < _matrix.size(); i++) {
      Pair pair = makePair(node, i);
      if (_matrix[pair.max][pair.min].active) {
        a.push_back(i);
      }
    }
    return a;
  }
};
